package leetcode_jz_offer.day8_dp;

/**
 * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第2天（股票价格 = 1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格
 **/

/**
 * max(price[j]-price[i])：最大差值。
 * 我们找出数组中两数字之间最大差值即可获得最大利润，并且第二个数>第一个数
 * 我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。
 * 那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice
 */
public class Num63_股票最大利润 {
//    public int maxProfit(int[] prices) {
//        int minPrice=Integer.MAX_VALUE;//初始化为整型最大值
//        int maxProfit=0;//最大利润（利润=当前遍历价格-最低价格，最大利润取最大值即可）
//        for (int i = 0; i < prices.length; i++) {
//            if(prices[i]<minPrice){//将最小值放入minPrice中
//                minPrice=prices[i];
//            }
//            if(prices[i]-minPrice>maxProfit){//当前遍历价格-最低价格>差价，更新差价
//                maxProfit=prices[i]-minPrice;
//            }
//        }
//        return maxProfit;
//    }
    //方法2：动态规划

    /**
     * 定义状态：dp[i]:以prices[i]为结尾的子数组的最大利润（即前i日的最大利润）
     * 转移方程：前i日最大利润=前i-1日最大利润dp[i-1]和第i日最大利润中的较大值
     * dp[i]=max(dp[i−1],prices[i]−min(prices[0:i]))
     */
    public int maxProfit(int[] prices) {
        int minPrice=Integer.MAX_VALUE;//购入的最小价格
        int profit=0;//利润
        for (int price : prices) {//price的值直接是数组中元素的值
            minPrice=Math.min(minPrice,price);//最小购入价格
            profit=Math.max(profit,price-minPrice);//右profit是上一循环中的差价，price-minPrice是当前购入值与最小值的差价，比较大者给profit
        }
        return profit;
    }

}
